{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Highest Altitude"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestAltitude"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到最高海拔"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一个自行车手打算进行一场公路骑行，这条路线总共由 <code>n + 1</code> 个不同海拔的点组成。自行车手从海拔为 <code>0</code> 的点 <code>0</code> 开始骑行。</p>\n",
    "\n",
    "<p>给你一个长度为 <code>n</code> 的整数数组 <code>gain</code> ，其中 <code>gain[i]</code> 是点 <code>i</code> 和点 <code>i + 1</code> 的 <strong>净海拔高度差</strong>（<code>0 <= i < n</code>）。请你返回 <strong>最高点的海拔</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>gain = [-5,1,5,0,-7]\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>海拔高度依次为 [0,-5,-4,1,1,-6] 。最高海拔为 1 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>gain = [-4,-3,-2,-1,4,3,2]\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>海拔高度依次为 [0,-4,-7,-9,-10,-6,-3,-1] 。最高海拔为 0 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == gain.length</code></li>\n",
    "\t<li><code>1 <= n <= 100</code></li>\n",
    "\t<li><code>-100 <= gain[i] <= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-highest-altitude](https://leetcode.cn/problems/find-the-highest-altitude/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-highest-altitude](https://leetcode.cn/problems/find-the-highest-altitude/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[-5,1,5,0,-7]', '[-4,-3,-2,-1,4,3,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestAltitude(self, gain: List[int]) -> int:\n",
    "        return max(accumulate([0]+gain))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestAltitude(self, gain: List[int]) -> int:\n",
    "        lst = [0]\n",
    "        high = 0\n",
    "        while len(gain) != 0:\n",
    "            high += gain.pop(0)\n",
    "            lst.append(high)\n",
    "        max1 = lst[0]\n",
    "        return max(lst)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestAltitude(self, gain: List[int]) -> int:\n",
    "        ret, total = 0, 0\n",
    "        for x in gain:\n",
    "            total += x\n",
    "            ret = max(ret, total)\n",
    "        return ret    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestAltitude(self, gain: List[int]) -> int:\n",
    "        return max(accumulate([0] + gain))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestAltitude(self, gain: List[int]) -> int:\n",
    "        return max(accumulate([0] + gain))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestAltitude(self, gain: List[int]) -> int:\n",
    "        haba= [0]*len(gain)\n",
    "        for index in range(1,len(gain)):\n",
    "            haba[index] = haba[index-1] + gain[index-1]\n",
    "        haba.append(haba[-1]+gain[-1])\n",
    "        print(\"haba\", haba)\n",
    "        return max(haba)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestAltitude(self, gain: List[int]) -> int:\n",
    "        ans = total = 0\n",
    "        for x in gain:\n",
    "            total += x\n",
    "            print(ans, total)\n",
    "            ans = max(ans, total)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestAltitude(self, gain: List[int]) -> int:\n",
    "        res = pre_sum = 0\n",
    "        for i in gain:\n",
    "            pre_sum += i\n",
    "            res = max(res, pre_sum)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestAltitude(self, gain: List[int]) -> int:\n",
    "        n = len(gain) + 1\n",
    "        # altitude = [0] * n\n",
    "\n",
    "        max_altitude = 0\n",
    "        # last_altitude = 0\n",
    "        current_altitude = [0]\n",
    "        for i in range(1, n):\n",
    "            # altitude[i] = altitude[i-1] + gain[i-1]\n",
    "            current_altitude[0] += gain[i-1]\n",
    "            max_altitude = max(max_altitude, current_altitude[0])\n",
    "            # last_altitude = current_altitude\n",
    "        \n",
    "        return max_altitude"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestAltitude(self, gain: List[int]) -> int:\n",
    "        ans = 0\n",
    "        tmp = 0\n",
    "        for num in gain:\n",
    "            tmp+=num\n",
    "            ans = max(ans,tmp)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
